/*
	aco-netdesign -- Ant colony optimization solution to network design problem

	Copyright (C) 2008 Jeffrey Sharkey, http://jsharkey.org/
	
	Developed by Jeffrey Sharkey as part of his thesis work at Montana State
	University. His work was sponsored by the Western Transportation Institute,
	and was guided by advisor Doug Galarus. Other valuable guidance was
	provided by Dr. Bill Jameson and Gary Schoep. 

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.
	
	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.
	
	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#pragma once

#include <math.h>
#include <assert.h>

#include <iostream>
#include <fstream>

#include <string>
#include <list>
#include <map>

using namespace std;

#include "graph.h"




class Solution : public Path, public Tagged {
public:
	map<Vertex*, double> bandwidth;
	bool invalid;
	
	Solution();
	virtual ~Solution();
	
	void saveSimple(Graph* g, string filename);
	void save(Graph* g, string filename);
	void saveRaw(Graph* g, string filename);


inline void localSearch(Graph* g) {

// do a local search to simplify the search
// try swapping two given links if we can maximize the margin

// for two given terminal vertexes, see if swapping their edges will give us better overall margin

cout << "localSearch: |E|=" << edges.size() << endl;

TimeRemaining* t = new TimeRemaining((int)pow(g->terminal.size(),2)/2, 2);

int swaps = 0, considered = 0;

ulist<Vertex*>::iterator i;
for(i = g->terminal.begin(); i != g->terminal.end(); i++) {
	// find the edge for this node
	Vertex* vertexi = *i;
	Edge* edgei = findEdge(g, vertexi);
	Vertex* vertexi2 = edgei->adjacent(vertexi);

	ulist<Vertex*>::iterator j;
	for(j = g->terminal.begin(); j != g->terminal.end(); j++) {
		Vertex* vertexj = *j;
		if(vertexj->id <= vertexi->id) continue;
		Edge* edgej = findEdge(g, vertexj);
		Vertex* vertexj2 = edgej->adjacent(vertexj);

		// ensure that the opposite edges actually exist
		Edge* opposite1 = g->findEdge(vertexi, vertexj2);
		Edge* opposite2 = g->findEdge(vertexj, vertexi2);

		t->increment();

		if(opposite1 == NULL || opposite2 == NULL) continue;

		// for margin, higher signal is better
		double before = edgei->margin + edgej->margin;
		double after = opposite1->margin + opposite2->margin;

		//cout << "thinking about before=" << before << " compared to after=" << after << endl; cout.flush();
		considered++;

		// if there is benefit, then actually perform the edge swap
		if(after > before) {
			edges.purge(edgei);
			edges.purge(edgej);
			edges.insert(opposite1);
			edges.insert(opposite2);
			swaps++;
//cout << "#" << endl; cout.flush();
		}

	}
}

cout << "localSearch: |E|=" << edges.size() << endl;
cout << "localSearch: performed " << swaps << " swaps out of " << considered << " considered" << endl;





}


	inline void saveVisual(Graph* g, string filename) {

// dump graph out to graphml file for later visualization
ofstream out(filename.c_str(), ofstream::out);
out.precision(8);

out << "<?xml version=\"1.0\" encoding=\"UTF-8\"?><graphml xmlns=\"http://graphml.graphdrawing.org/xmlns/graphml\" xmlns:y=\"http://www.yworks.com/xml/graphml\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xsi:schemaLocation=\"http://graphml.graphdrawing.org/xmlns/graphml http://www.yworks.com/xml/schema/graphml/1.0/ygraphml.xsd\">" << endl;
out << "<key id=\"d0\" for=\"node\" yfiles.type=\"nodegraphics\"/><graph id=\"G\" edgedefault=\"undirected\">" << endl;

// walk through and count up each layer type
cout << "saveVisual: counting up layers" << endl; cout.flush();
int counts[5] = { 0,0,0,0,0 };
map<int,Vertex*>::iterator it;
for(it = g->vertexes.begin(); it != g->vertexes.end(); it++) {
	Vertex* v = (*it).second;
	counts[v->layer]++;
}


// dump out all nodes in specific size
cout << "saveVisual: dumping out all vertexes" << endl; cout.flush();
int progress[5] = { 0,0,0,0,0 };
for(it = g->vertexes.begin(); it != g->vertexes.end(); it++) {
	Vertex* v = (*it).second;

	double x = 20000*(double)progress[v->layer] / (double)counts[v->layer];
	double y = 10000*(double)v->layer / 5;

// only dump out node if included in solution
if(vertexes.contains(v)) {
	out << "<node id=\"n" << v->id << "\"><data key=\"d0\"><y:ShapeNode><y:Geometry x=\"" << x << "\" y=\"" << y << "\" width=\"15\" height=\"15\" /></y:ShapeNode></data></node>" << endl;
}

	progress[v->layer]++;
}


cout << "saveVisual: dumping out all edges" << endl; cout.flush();
map<int,Edge*>::iterator j;
for(j = g->edges.begin(); j != g->edges.end(); j++) {
	Edge* e = (*j).second;

// only dump out edge if included in solution
if(edges.contains(e)) {
	out << "<edge source=\"n" << e->u->id << "\" target=\"n" << e->v->id << "\"/>" << endl;
}


}

out << "</graph></graphml>" << endl;



	}


};


class Solver {
public:
	Graph* g;
	Lookup* look;
	
	Solver(Graph* g_, Lookup* look_);
	virtual ~Solver();

	virtual Solution* singleSolution() = 0;
	
};


class SolverApprox : public Solver {
public:
	SolverApprox(Graph* g_, Lookup* look_);
	virtual ~SolverApprox();
	
	Solution* singleSolution();
	
};




